package _6subset;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Gong Cheng
 * @date 2021/1/14 10:16 上午
 **/
public class subsets78 {
    /**
     * 使用动态规划
     * 首先创建返回的List，放入一个空集合，
     * 遍历原数组，获得各个元素
     * 将List中的所有元素与遍历出的元素组合，再放入List;
     * 返回List
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int i = 0; i <nums.length ; i++) {
            int resSize = res.size();
            for (int j = 0; j <resSize ; j++) {
                List<Integer> arrays = new ArrayList<>(res.get(j));
                arrays.add(nums[i]);
                res.add(arrays);
            }
        }
        return res;
    }



    /**
     * 迭代法实现解题
     * 记原序列中元素的总数为 nn。原序列中的每个数字 a_ia
     * i
     * ​
     *   的状态可能有两种，即「在子集中」和「不在子集中」。我们用 11 表示「在子集中」，00 表示不在子集中，那么每一个子集可以对应一个长度为 nn 的 0/10/1 序列，第 ii 位表示 a_ia
     * i
     * ​
     *   是否在子集中。例如，n = 3n=3 ，a = \{ 5, 2, 9 \}a={5,2,9} 时：
     *
     */
    public List<List<Integer>> subsets2(int[] nums){
        List<Integer> t = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();


        int n = nums.length;
        for(int mask = 0; mask < (1 << n);++mask){
            t.clear();
            for(int i = 0; i < n ; ++i){
                if((mask & (1<<i))!= 0){
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
    /**
     * 递归法实现子集枚举
     */
    List<Integer> t = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets3(int[] nums){
        dfs(0, nums);
        return ans;
    }

    public void dfs(int cur, int[] nums){
        if(cur == nums.length){
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[cur]);
        dfs(cur + 1,nums);
        t.remove(t.size() - 1);
        dfs(cur + 1,nums);
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3};
        System.out.println(new subsets78().subsets3(nums));
    }
}
